package leetcode.editor.cn;

//给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
// 
//
// 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
//输出："apple"
// 
//
// 示例 2： 
//
// 
//输入：s = "abpcplea", dictionary = ["a","b","c"]
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// 1 <= dictionary.length <= 1000 
// 1 <= dictionary[i].length <= 1000 
// s 和 dictionary[i] 仅由小写英文字母组成 
// 
// Related Topics 数组 双指针 字符串 排序 👍 276 👎 0

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

//Java：通过删除字母匹配到字典里最长单词
public class LongestWordInDictionaryThroughDeleting_524{
    public static void main(String[] args) {
        Solution solution = new LongestWordInDictionaryThroughDeleting_524().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        dictionary.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length()==o2.length()){
                    return o1.compareTo(o2);
                }else{
                    return o2.length()-o1.length();
                }
            }
        });
//        System.out.println(dictionary);
        for (String dic : dictionary) {
            int len1=dic.length(),len2=s.length(),i=0,j=0;
            while(i<len1 && j<len2){
                if(dic.charAt(i)==s.charAt(j)){
                    i++;
                }
                j++;
            }
            if(i==len1) return dic;
        }
        return "";
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
